//1.笨方法


// 根右左相当于把数镜像（翻转）遍历了一遍

class Solution {
public:
    vector<int> leftfirst;
    vector<int> rightfirst;

    void leftPreOrder(TreeNode* root)  {
        if(root==nullptr) {
            leftfirst.push_back(111); //存储空结点
            return ;
        }
            
        leftfirst.push_back(root->val);
        leftPreOrder(root->left);
        leftPreOrder(root->right);

    }
    void rightPreOrder(TreeNode* root) { 
        if(root==nullptr) {
            rightfirst.push_back(111);//存储空结点
            return ;
        }
        rightfirst.push_back(root->val);
        rightPreOrder(root->right);
        rightPreOrder(root->left);

    }

    bool isSymmetric(TreeNode* root) {
        leftPreOrder(root);
        rightPreOrder(root);

        if(leftfirst.size() != rightfirst.size())
            return false;
        for(int i=0;i<leftfirst.size(); ++i) {
            if(leftfirst[i] != rightfirst[i])
                return false;
        }
        return true;
    }
};

//2.笨方法--分别记录反转前后的值是否一样
class Solution {
public:
    vector<int> begin;
    vector<int> end;
    vector<int> action(TreeNode* root, vector<int>& act) {
        if(root==nullptr) {
            act.push_back(111);
            return {};
        }
           
        
        act.push_back(root->val);
        action(root->left,act);
        action(root->right,act);
        return act;
    }
    vector<int> fanzhuan(TreeNode* root) {
        if(root==nullptr)        
            return {};
        
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
             
        fanzhuan(root->left);
        fanzhuan(root->right);
        return {};
    }




    bool isSymmetric(TreeNode* root) {
        vector<int> begin1;
        vector<int> end1;
        begin = action(root,begin1);
        fanzhuan(root);
        end = action(root,end1);
        for(int i=0;i<begin1.size();++i) {
            if(begin[i] != end[i])
                return false;
        }
        return true;
        
    }
};

//3.递归
/*

该问题可以转化为：两个树在什么情况下互为镜像？
如果同时满足下面的条件，两个树互为镜像：
它们的两个根结点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称

*/
class Solution {
public:
    bool isMirror(TreeNode* _left, TreeNode* _right) {
        if(_left==nullptr && _right==nullptr)
            return true;
        if(_left==nullptr || _right==nullptr)
            return false;

        return _left->val==_right->val 
        && isMirror(_left->left, _right->right) && isMirror(_left->right, _right->left);


    }
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr)
            return true;
        return isMirror(root->left,root->right) ;
    }
};




